package main

import "fmt"

func main() {
	fmt.Printf("returnAllSubString(\"abc\"): %v\n", returnAllSubString("abbc"))
}

func returnAllSubString(s string) []string {
	hashSet := make(map[string]struct{})
	//path := []byte{}
	//dfs1(s, 0, path, hashSet)
	path := make([]byte, len(s))
	dfs2(s, 0, path, 0, hashSet)
	ans := []string{}
	for s, _ := range hashSet {
		ans = append(ans, s)
	}
	return ans
}

func dfs1(s string, cur int, path []byte, hashSet map[string]struct{}) {
	if cur == len(s) {
		hashSet[string(path)] = struct{}{}
		return
	}
	path = append(path, s[cur])
	dfs1(s, cur+1, path, hashSet)
	path = path[:len(path)-1]
	dfs1(s, cur+1, path, hashSet)
}

func dfs2(s string, cur int, path []byte, size int, set map[string]struct{}) {
	if cur == len(s) {
		set[string(path[:size])] = struct{}{}
		return
	}
	path[size] = s[cur]
	dfs2(s, cur+1, path, size+1, set)
	dfs2(s, cur+1, path, size, set)
}
